package dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个m x n 二维字符网格board和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
 * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
 * https://leetcode-cn.com/problems/word-search-ii/
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2021/2/17 17:59
 */
public class FindWords {
    public static void main(String[] args) {

    }

    private static boolean flag;

    public List<String> findWords(char[][] board, String[] words) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            flag = false;
            char[] chars = word.toCharArray();
            boolean[][] stack = new boolean[board.length][board[0].length];
            if (chars.length > board.length * board[0].length) {
                continue;
            }
            for (int i = 0; i < board.length && !flag; i++) {
                for (int j = 0; j < board[i].length && !flag; j++) {
                    if (chars[0] == board[i][j]) {
                        stack[i][j] = true;
                        backtracking(1, i, j, chars, board, stack);
                        stack[i][j] = false;
                        if (flag) {
                            list.add(word);
                        }
                    }


                }
            }
        }
        return list;
    }

    private static void backtracking(int n, int i, int j, char[] chars, char[][] board, boolean[][] stack) {
        if (flag) {
            return;
        }
        if (n == chars.length) {
            flag = true;
            return;
        }
        if (i < board.length - 1 && chars[n] == board[i + 1][j] && !stack[i + 1][j]) {
            stack[i + 1][j] = true;
            backtracking(n + 1, i + 1, j, chars, board, stack);
            stack[i + 1][j] = false;
        }
        if (i > 0 && chars[n] == board[i - 1][j] && !stack[i - 1][j]) {
            stack[i - 1][j] = true;
            backtracking(n + 1, i - 1, j, chars, board, stack);
            stack[i - 1][j] = false;
        }
        if (j < board[0].length - 1 && chars[n] == board[i][j + 1] && !stack[i][j + 1]) {
            stack[i][j + 1] = true;
            backtracking(n + 1, i, j + 1, chars, board, stack);
            stack[i][j + 1] = false;
        }
        if (j > 0 && chars[n] == board[i][j - 1] && !stack[i][j - 1]) {
            stack[i][j - 1] = true;
            backtracking(n + 1, i, j - 1, chars, board, stack);
            stack[i][j - 1] = false;
        }
    }
}
